from 第21天.数据结构 import LinkedList, Node


class HashBucketLinkedList(LinkedList):
    def get_by_key(self, key) -> Node:
        i, target_node = self._get_target_node_by_key(key)
        if target_node is None:
            return None
        return target_node

    def delete_by_key(self, key):
        i, target_node = self._get_target_node_by_key(key)
        if target_node is None:
            return
        return self.delete(i)

    def _get_target_node_by_key(self, key):
        node = self.start_node
        i = 0
        while node.get_next_node() is not None:
            if node.get_item()[0] == key:
                return node
            i += 1
        return i, None


class HashBucket:
    def __init__(self, hash_key):
        self.hash_key = hash_key
        self.linked_list = HashBucketLinkedList()

    def add(self, key, value):
        target_node = self.linked_list.get_by_key(key)
        if target_node is None:
            self.linked_list.append((key, value))
        else:
            target_node.modify_item((key, value))

    def get(self, key):
        return self.linked_list.get_by_key(key)

    def delete(self, key):
        self.linked_list.delete_by_key(key)


class HashTable:
    def __init__(self):
        self.hash_key_list = []

    @classmethod
    def _hash(cls, key):
        return hash(key)

    def add(self, key, value):
        """
        哈希表中增加键值对
        :param key:
        :param value:
        :return:
        """
        hash_key = self._hash(key)
        target_hash_bucket = self._get_bucket(hash_key)
        if target_hash_bucket is None:
            target_hash_bucket = HashBucket(hash_key)
        target_hash_bucket.add(key, value)

    def get(self, key):
        """
        根据键查询值
        :param key:
        :return:
        """
        hash_key = self._hash(key)
        target_hash_bucket = self._get_bucket(hash_key)
        if target_hash_bucket is None:
            return None
        return target_hash_bucket.get(key)

    def delete(self, key):
        """
        删除指定键的键值对
        :param key:
        :return:
        """
        hash_key = self._hash(key)
        target_hash_bucket = self._get_bucket(hash_key)
        if target_hash_bucket is None:
            return
        target_hash_bucket.delete(key)

    def _get_bucket(self, hash_key) -> HashBucket:
        """
        根据 hash 后的 key 获取指定的 hash 桶
        :param hash_key:
        :return:
        """
        for bucket in self.hash_key_list:
            if bucket.hask_key == hash_key:
                return bucket
        return None
